package com.salim.leetcode.$47;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

@Slf4j
public class PermutationsII {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> remain = new ArrayList<Integer>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            remain.add(nums[i]);
        }
        for(int i=0;i<nums.length;i++){
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            List<Integer> subResult = new ArrayList<>();
            boolean[] used = new boolean[nums.length];
            used[i] = true;
            subResult.add(nums[i]);
            loop(used,subResult);
            used[i] = false;
        }
        return result;
    }

    public void loop(boolean[] used,List<Integer> lastList){
        if(lastList.size()==remain.size()){
            result.add(lastList);
            return;
        }
        for(int i=0;i<used.length;i++){
            if(used[i]){
                continue;
            }
            if(i>0 &&remain.get(i-1).equals(remain.get(i)) && !used[i-1]) {
                continue;
            }
            List<Integer> subResult = new ArrayList<>(lastList);
            subResult.add(remain.get(i));
            used[i] = true;
            loop(used,subResult);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        PermutationsII p = new PermutationsII();
        log.info("PermutationsII输出结果1：{}", p.permuteUnique(new int[]{1,1,3}));
    }
}
